package huawei;

/**
 * 题目描述
 * 近些年来，我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨（编号1-N），排成一排。
 * 一个月后，有M棵胡杨未能成活。现可补种胡杨K棵，请问如何补种（只能补种，不能新种），
 * 可以得到最多的连续胡杨树？
 * <p>
 * 输入描述
 * N 总种植数量 1<=N<=100000
 * M 未成活胡杨数量 1<=M<=N
 * M 个空格分隔的数，按编号从小到大排列
 * K 最多可以补种的数量 0<=K<=M
 * <p>
 * 输出描述
 * 最多的连续胡杨棵树
 */

public class N1补种未成活胡杨 {
    public static void main(String[] args) {
        System.out.printf("123    " + solution(10, 3, new int[]{2, 4, 7}, 1));
    }

    public static int solution(int n, int m, int[] indies, int k) {
        int maxLength = 0;
        //计算两个未成活的距离
        for (int i = 0; i <= m - k; i++) {
            if (i == 0) {
                maxLength = indies[k] - 1;
            } else if (i == m - k) {
                maxLength = Math.max(maxLength, n - indies[m - k - 1]);
            } else {
                maxLength = Math.max(maxLength, indies[i + k] - indies[i - 1] - 1);
            }
        }
        return maxLength;
    }

}
